class Solution(object):
    def partition(self, s):
        """
        :type s: str
        :rtype: List[List[str]]
        """
        length = len(s)
        DP = [[False for _ in range(length)] for _ in range(length)]

        def is_huiwen(s):
            if s == s[::-1]:
                return True
            else:
                return False

        for i in range(length):
            for j in range(i, length):
                DP[i][j] = is_huiwen(s[i: j + 1])

        return_list = []
        now_list = []

        def search(i):
            for j in range(i + 1, length + 1):
                if DP[i][j - 1]:
                    now_list.append(s[i: j])
                    if j == length:
                        return_list.append(now_list.copy())
                    else:
                        search(j)
                    del now_list[-1]

        search(0)
        return return_list


data = Solution()
s = 'accbee'
print(data.partition(s))